package backTrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Class51_1 {

     List<List<String>> res= new ArrayList<>();

    public   List<List<String>> solveNqueens(int n){
        char[][] chessboard=new char[n][n];
        for (char[] c:chessboard){
            Arrays.fill(c,'.');
        }
        backTrack(n,0,chessboard);
        return  res;
    }


    public  void  backTrack(int n,int row,char[][] chessboard){
        if (row==n){
            res.add(Array2List(chessboard));
            return;
        }

        for (int col = 0; col <n ; col++) {
            if (isValid(row,col,n,chessboard)){
                chessboard[row][col]='Q';
                backTrack(n,row+1,chessboard);
                chessboard[row][col]='.';

            }

        }
    }

    public List Array2List(char[][] chessboard){
        ArrayList<String > list = new ArrayList<>();
        for (char[] c: chessboard
             ) {
            list.add(String.copyValueOf(c));
        }

return  list;

    }
    public  boolean isValid(int row,int col,int n,char[][] chessboard){
        //  CKG TODO 2023/4/23: 检查列
        for (int i = 0; i < row; i++) {
            if (chessboard[i][col]=='Q'){
                return  false;
            }
        }

        //  CKG TODO 2023/4/23: 检查45度对脚线
        for (int i = row-1,j=col-1; i>=0&&j>=0 ; i--,j--) {
            if (chessboard[i][j]=='Q'){
                return  false;
            }
        }

        //  CKG TODO 2023/4/23:   特点以上的检查都检查当前行前面的行数 因为下面的行数还没有插入皇后
        for (int i = row-1,j=col+1; i >=0&&j<=n-1 ; i--,j++) {
            if (chessboard[i][j]=='Q'){
                return false;
            }

        }




        return  true;
    }

    public static void main(String[] args) {
        Class51_1 class51_1 = new Class51_1();
        System.out.println(class51_1.solveNqueens(4).toString());

    }




}
